cc.Class({
    extends: cc.Component,

    properties: {
        cellPrefab:{
            default:null,
            type:cc.Prefab
        },

        noticeLabel:{
            default:null,
            type:cc.Label
        }
    },

    onLoad: function () {
        //total loop times
        this.roundCount = 0

        //for showing test
        let wOffset = -cc.winSize.width/2+10
        let hOffset = -cc.winSize.height/2+10

        //generate map array
        let mapArray = []
        for(let i=0;i<80;i++)
        {
            for(let j=0;j<50;j++)
            {
                let pos = cc.v2(i,j)

                let newNode = cc.instantiate(this.cellPrefab)
                let truePos = cc.v2(pos.x * (newNode.width*1.2)+wOffset,pos.y * (newNode.height*1.2)+hOffset)
                newNode.position = truePos
                this.node.addChild(newNode)

                pos._node = newNode
                mapArray.push(pos)
            }
        }


        //generate a vertical block
        for(let i=0;i<40;i++){

            let block1 = this._getCellFromMap(mapArray,cc.v2(20,i))
            block1._node.color = cc.color(255,0,0,255)
            block1._blocked = true
        }

        //generate a horizontal block
        for(let i=20;i<60;i++){

            let block1 = this._getCellFromMap(mapArray,cc.v2(i,39))
            block1._node.color = cc.color(255,0,0,255)
            block1._blocked = true
        }


        //generate second vertical block
        for(let i=39;i>10;i--){

            let block1 = this._getCellFromMap(mapArray,cc.v2(39,i))
            block1._node.color = cc.color(255,0,0,255)
            block1._blocked = true
        }

        let startCell = this._getCellFromMap(mapArray,cc.v2(0,0))
        let targetCell = this._getCellFromMap(mapArray,cc.v2(34,21))

        startCell._node.color = cc.color(0,0,0,255)
        targetCell._node.color = cc.color(0,255,255,255)

        let path = this.findPath(mapArray,startCell,targetCell)
        this.noticeLabel.string = "总共查询了"+this.roundCount+"次"

        //show final path
        for(let i=0;i<path.length;i++)
        {
            let tmpCell = path[i]
            tmpCell._node.color = cc.Color.YELLOW
        }

        //show start and destination cell
        startCell._node.color = cc.Color.GREEN
        targetCell._node.color = cc.Color.RED
    },

    /**
     * 开始寻路
     * @param mapArray
     * @param startCell
     * @param targetCell
     * @returns {*}
     */
    findPath:function (mapArray,startCell,targetCell) {

        //临时变量
        this._openArray = []
        this._closeArray = []
        for(let i=0;i<mapArray.length;i++){
            mapArray[i]._g = 0
            mapArray[i]._h = 0
            mapArray[i]._f = 0
        }

        let pathArray = this._doFind(mapArray,startCell,targetCell)

        //清除临时变量
        this._openArray = []
        this._closeArray = []
        for(let i=0;i<mapArray.length;i++){
            mapArray[i]._g = 0
            mapArray[i]._h = 0
            mapArray[i]._f = 0
        }

        return pathArray
    },

    /**
     * 设置目标格子周围格子的G和H，以及父格
     * @param parentPos
     */
    setChildCells:function (mapArray, parentPos, destinationCell) {
        if(!parentPos){
            cc.warn("can't find cell :",parentPos)
            return
        }

        this.roundCount ++

        let cX = parentPos.x
        let cY = parentPos.y

        let arroundCells = []
        let upPos = this._getCellFromMap(mapArray,cc.v2(cX,cY+1))
        let downPos = this._getCellFromMap(mapArray,cc.v2(cX,cY-1))
        let leftPos = this._getCellFromMap(mapArray,cc.v2(cX-1,cY))
        let rightPos = this._getCellFromMap(mapArray,cc.v2(cX+1,cY))

        if(upPos && this.isCellBlocked(upPos)){
            let idxInOpen = this._openArray.indexOf(upPos)
            if(idxInOpen > -1)
                this._openArray.splice(idxInOpen,1)
            this._closeArray.push(upPos)
        }
        if(downPos && this.isCellBlocked(downPos)){
            let idxInOpen = this._openArray.indexOf(downPos)
            if(idxInOpen > -1)
                this._openArray.splice(idxInOpen,1)
            this._closeArray.push(downPos)
        }
        if(leftPos && this.isCellBlocked(leftPos)){
            let idxInOpen = this._openArray.indexOf(leftPos)
            if(idxInOpen > -1)
                this._openArray.splice(idxInOpen,1)
            this._closeArray.push(leftPos)
        }
        if(rightPos && this.isCellBlocked(rightPos)){
            let idxInOpen = this._openArray.indexOf(rightPos)
            if(idxInOpen > -1)
                this._openArray.splice(idxInOpen,1)
            this._closeArray.push(rightPos)
        }

        if(upPos && !this._isCellClosed(upPos)){
            this.updateCell(upPos,parentPos,destinationCell)
            this._pushInOpenArray(upPos)
            arroundCells.push(upPos)
        }
        if(downPos && !this._isCellClosed(downPos)){
            this.updateCell(downPos,parentPos,destinationCell)
            this._pushInOpenArray(downPos)
            arroundCells.push(downPos)
        }
        if(leftPos && !this._isCellClosed(leftPos)){
            this.updateCell(leftPos,parentPos,destinationCell)
            this._pushInOpenArray(leftPos)
            arroundCells.push(leftPos)
        }
        if(rightPos && !this._isCellClosed(rightPos)){
            this.updateCell(rightPos,parentPos,destinationCell)
            this._pushInOpenArray(rightPos)
            arroundCells.push(rightPos)
        }

        return arroundCells
    },

    isCellBlocked:function (cell) {
        if(cell._blocked)
            return true
        return false
    },

    _isCellClosed:function (cell) {
        return cell && this._closeArray.indexOf(cell) > -1
    },

    _pushInOpenArray:function (cell) {

        let oldIdx = this._openArray.indexOf(cell)
        if(oldIdx > -1)
            return

        if(this._openArray.length === 0)
        {
            this._openArray.push(cell)
        }
        else
        {
            let smaller = false
            for(let i=0;i<this._openArray.length;i++)
            {
                let cellF = cell._g + cell._h
                let tmpCell = this._openArray[i]
                let tmpF = tmpCell._g + tmpCell._h
                if(cellF <= tmpF){
                    smaller = true
                    this._openArray.splice(i,0,cell)
                    break
                }
            }

            if(!smaller)
                this._openArray.push(cell)
        }
    },

    checkIsDestination:function (cell,destinationCell) {
        return cell === destinationCell
    },

    updateCell:function (cell, parentCell, destinationCell) {
        if(!cell)
            return

        let newG = parentCell._g + 1
        let newH = this.getManhattanDistance(cell,destinationCell)
        let newF = newG + newH

        let oldG = cell._g
        let oldH = cell._h
        let oldF = oldG + oldH

        if(!oldF || newG <= oldG){
            cell._g = newG
            cell._h = newH
            cell._parentCell = parentCell
        }
    },

    getManhattanDistance:function (cell, destinationCell) {
        let offsetX = Math.abs(cell.x - destinationCell.x)
        let offsetY = Math.abs(cell.y - destinationCell.y)

        return offsetX + offsetY
    },

    _doFind:function (mapArray,startCell,targetCell) {
        this._openArray.splice(this._openArray.indexOf(startCell),1)
        this._closeArray.push(startCell)

        let arroundCells = this.setChildCells(mapArray,startCell,targetCell)

        //check reach destination
        for(let i=0;i<arroundCells.length;i++)
        {
            let tmpCell = arroundCells[i]
            if(tmpCell && this.checkIsDestination(tmpCell,targetCell)){
                let finalPathCells = []
                this._getPathCellArray(targetCell,finalPathCells)
                return finalPathCells
            }
        }

        let minFCell = this.getMinFCell()
        return this._doFind(mapArray,minFCell,targetCell)
    },

    _getPathCellArray:function (destinationCell,pathCells) {
        this._pushParentInArray(destinationCell,pathCells)
    },

    _pushParentInArray:function (childCell,pathCells) {
        let parentCell = childCell._parentCell
        if(parentCell)
            pathCells.push(parentCell)
        else
            return

        this._pushParentInArray(parentCell,pathCells)
    },

    getMinFCell:function () {
        return this._openArray[0]
    },

    _getCellFromMap:function (mapArray, targetCell) {
        let targetX = targetCell.x
        let targetY = targetCell.y
        for(let i=0;i<mapArray.length;i++)
        {
            if(mapArray[i].x === targetX && mapArray[i].y === targetY)
                return mapArray[i]
        }
        return null
    },
});
